﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0121_OddEvenList : IAlgorithm
    {
        // 奇偶链表

        // 给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
        // 第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。
        // 请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
        // 你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

        // 提示:
        //  n ==  链表中的节点数
        //  0 <= n <= 10^4
        //  -10^6 <= Node.val <= 10^6

        public void Test()
        {
            // 算法参数定义
            var head = new ListNode(1)
            {
                next = new ListNode(2)
                {
                    next = new ListNode(3)
                    {
                        next = new ListNode(4)
                        {
                            next = new ListNode(5)
                        }
                    }
                }
            };
            // 算法执行与打印
            var res = OddEvenList(head);
            while (res != null)
            {
                Console.Write(res.val + " ");
                res = res.next;
            }
        }

        // 1 2 3 4 5
        // 1 3 2 4 5
        // 1 3 5 2 4
        // 算法
        public ListNode OddEvenList(ListNode head)
        {
            ListNode l = head, r = head;
            bool oddFlag = true;
            while (r != null)
            {
                if (!oddFlag && r.next != null)
                {
                    var temp1 = l.next;
                    var temp2 = r.next.next;
                    l.next = r.next;
                    l.next.next = temp1;
                    r.next = temp2;
                    l = l.next;
                }
                else
                {
                    r = r.next;
                }
                oddFlag = !oddFlag;
            }
            return head;
        }

        public ListNode OddEvenList1(ListNode head)
        {
            if (head == null || head.next == null)
                return head;
            ListNode oddHead = head;
            ListNode oddCur = oddHead;
            ListNode evenHead = head.next;
            ListNode evenCur = evenHead;
            while (evenCur != null && evenCur.next != null)
            {
                oddCur.next = oddCur.next.next;
                evenCur.next = evenCur.next.next;
                oddCur = oddCur.next;
                evenCur = evenCur.next;
            }
            oddCur.next = evenHead;
            return oddHead;
        }
    }
}
